import gmpy2
import libnum

n1 = 22036096414750333101406538757625812613248444424049684758772058140377463618250795867832853117902163257003301132932490853355450673043991381637053778653821758783435921283322439267628837074056789021611782010444749024512216306961829453158759193969454712080047205883631153040900193575534288719429526169135614695862857156639195562501217424283401364740789214390377624598500939079307163832197534297642842744345373413423859103414676878739674227554029537817890874031594311152843060524913028526429344172693584167398664817727426767686424415189580527939256633114120720308173788544194669684834369132677253418971615644691719536820433
n2 = 17251653165250011947306159769694143433212298910745609670733920118632739529605426957617875166211610794383631191273183964010346725508667657137931394653419082978603166138439632713627832321960586938891805262605225424775586397813147240201440036009395991700175612039074317131837185920131565272816639771739150718839592250080325774556601865770352479323350280393818365902570673799584200153846520860657815432981116910233453207519365604533077996449249223280685559491369393277114405166293011856168173778428700718404816038991911974902005969923746846815798515831172402122367026339135245751136695128279659872423027539333024854133659
c1 = 1408937404754902028814920445701404613476983383738408959873219805755187459225302977012340464647741276263048769176603562703588286152102079561897286480939341184453940846603761664643956274520695676061184610702912592321357240109665885587701906369214592438887065694062151546241739122722790261888290706296747328780758965559093085406877315628139811554345214347799361309288949307776501119359571116522001853935560023530705364795364624152061166945046882418058831567088890277747158775876953662285842999920594778445526224560016361787941610542255000514402493843548068271595134879195073239601085319795505131267697387692179944010772
c2 = 12175155463891225370775786368564999885751076529394005420368968241428058465831204925081389807872272508968531564921996276054143112205083003561546962102395368677755381589762565680900651699885381615975236663522025080384481537727180649424984636506390139648492522347366656322729441290553251505232488994951243521740296115895651926783520321289129993169836271218322014443396220481361007479796234525990954874013729001502984583162486353287639655447340498584591591009224750835072707121652727119580764546240945763088815277130694950594020142961659318737857067755125666395542079926757603295535345281657293981259718286213812909191174
e = 65537

p = gmpy2.gcd(n1, n2)
print(p)
q = n1 // p
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c1, d, n1)
print(libnum.n2s(int(m)))
